NPS55-77-5 NAVAL POSTGRADUATE SCHOOL Monterey, California A DIFFUSION APPROXIMATION MODEL FOR A COMMUNICATION SYSTEM ALLOWING MESSAGE INTERFERENCE by Donald P. Gaver John P. Lehoczky February 1977 FEDDOCS D 208.14/2:NPS-55-77-5 red for public release; distribution unlimited red for: j.ice of Naval Research, Arlington, VA 22217 iUUlhY KNOX LIBRARY, OSTGRADUATE SCHOOL pA| |p 0^940 NAVAL POSTGRADUATE SCHOOL MONTEREY, CALIFORNIA Rear Admiral Isham Linder Superintendent Jack R. Borsting Provost The work reported herein was supported by the Office of Naval Research and the Defense Communication Agency at the Naval Post- graduate School. Reproduction of all or part of this report is authorized. This report was prepared by: / n / i UNCLASSIFIED *NOX LIBRARY EQUATE SCHOOL SECURITY CLASSIFICATION OF THIS PAGE (When Data Entered) REPORT DOCUMENTATION PAGE READ INSTRUCTIONS BEFORE COMPLETING FORM 1. REPORT NUMBER NPS55-77-5 2. GOVT ACCESSION NO. 3. RECIPIENT'S CATALOG NUMBER 4. TITLE (and Subtitle) A Diffusion Approximation Model for a Communication System Allowing Message Interference 5. TYPE OF REPORT ft PERIOD COVERED Technical Report 6. PERFORMING ORG. REPORT NUMBER 7. AUTHORfaj Donald P. Gaver and John P. Lehoczky B. CONTRACT OR GRANT NUMBERS 9. PERFORMING ORGANIZATION NAME AND ADDRESS Naval Postgraduate School Monterey, California 93940 10. PROGRAM ELEMENT. PROJECT, TASK AREA ft WORK UNIT NUMBERS 11. CONTROLLING OFFICE NAME AND ADDRESS Office of Naval Research Arlington, Virginia 22217 12. REPORT DATE February 1977 13. NUMBER OF PAGES 31 14. MONITORING AGENCY NAME a ADDRESSf// different Itom Controlling OHice) 15. SECURITY CLASS, (of thla report) Unclassified 15a. DECLASSIFICATION DOWNGRADING SCHEDULE 16. DISTRIBUTION ST ATEMENT (of this Report) Approved for public release; distribution unlimited. 17. DISTRIBUTION STATEMENT (of the abetract entered In Block 20, It different from Report) 18. SUPPLEMENTARY NOTES 19. KEY WORDS (Continue on reverse aide If neceaaary and Identify by block number; Communication systems, congestion theory, queueing, probability modeling 20. ABSTRACT (Continue on reverae aide If neceaaary and Identity by block number) Mathematical probability models are presented to describe the service furnished to messages approaching c communications chan- nels, on which messages in progress may be "destroyed" by an attempted access by a new message. Re-tries by destroyed mes- sages are modeled. Numerical results, using the models, are com- pared to simulations, validating model usefulness. dd ,; FORM ■,«, AN 73 1473 EDITION OF 1 NOV 65 IS OBSOLETE S/N 0102-014-6601 | UNCLASSIFIED SECURITY CLASSIFICATION OF THIS PAGE (When Data Entered) A DIFFUSION APPROXIMATION MODEL FOR A COMMUNICATION SYSTEM ALLOWING MESSAGE INTERFERENCE Donald P. Gaver Naval Postgraduate School John P. Lehoczky Carnegie-Mellon University 1 . Introduction and Problem Statement We study the operating characteristics of an element of a complex commun- ication system, the element consisting of c channels which service an arrival stream of messages. When a message arrives, it selects a channel at random and initiates a transmission (service) time of random duration. If by chance the channel selected is already occupied, i.e. is in the process of transmission, both messages may be "destroyed," i.e. terminated before com- pletion, and the channel reverts to an empty or open condition. The trans- mitters of the messages are capable of detecting the event of destruction, and following such an event go into a re -try or re-transmission population, from which they later make attempts to occupy a channel and eventually com- plete message transmission. We develop an approximate probability model to describe the performance of such a system. The approximation tends to become exact as the number of channels, c , becomes large (c-*») , but numerical studies indicate that it may be quite adequate for c near ten. The above problem bears close resemblance to a problem of packet switching of data on the ARPANET and, \/ery likely, on other satellite communications systems, as discussed in Kleinrock (1976), p. 362 ff. We choose to represent the various interacting populations of messages, i.e. those in process, and those in the re-try population, by means of stochastic differential equa- tions as was done by Gaver and Lehoczky (1976) for a related problem. 2. Mathematical Formulations: Model 1 Assume that messages arrive at a system of c channels according to a non-homogeneous Poisson process of rate cA(t) ; that is, the probability that a message arrives in (t, t+dt) is cX(t)dt + o(dt) . Each message then selects a channel at random; any particular channel , whether occupied or not, is selected with probability c~ . If the channel is unoccupied the message begins transmission; the probability that it completes in time (t, t+dt) is u(t)dt + o(dt) . Note that if y(t) = u , constant, the messages enjoy exponential service times, and if we wish to generate other, say Erlang, service times the device of phases, or extra artificial compart- ments, may be used, as in Gaver and Lehoczky (1976). If a message in progress on a channel is interrupted by the arrival of another message, both are assumed instantly destroyed, and the message initi- ators are transferred to a re- try population, R . A message that has entered R changes its status at time t with probability v(t)dt + o(dt) : with probability a(t) the change of status implies an attempt to re-transmit on a channel, and with probability a(t) = l-a(t) the change of status implies loss -- the message may no longer be worth transmitting. Our representation of the above setup is in terms of the following state variables. Q(t) = the number of messages being transmitted, i.e. occupying channels, at time t ; clearly 0 < £(t) =s c . (2.1) JR(t) = the number of messages in R at time t ; 0 < JR(t) < °° . L(t) = the total number of messages that have been lost by time t ; 0 < L(t) < °° • The state of the system is thus (£(t), R(t), Ljt)) , a discrete vector- valued Markov process, according to our earlier assumptions. We shall characterize this process approximately when c-**> , and shall in particular treat Q , R , and L as continuous stochastic processes, in fact as diffusion processes, see Arnold (1974). Here is a formalization of the transitions described earlier: Transition Probability (in t, t+dt) Q(t) (2, R, L) ■* (2+1, R. L) cA(t)[l- — ]dt 2(t) - (£-1, R+2, L) cX(t)— — dt -(£-l,R, L) y(t)£(t)dt (2.2) Q - (Q+l, R-l, L) v(t)a(t)[l-3R(t)dt #v/ ^-» c 2 ■* (fl"1' £+1» k) v(t)a(t)^(t)dt + (Q, R-l, L+l) v(t)a(t)R(t)dt Other transitions have negligible probability of occurring in (t, t+dt) . Now in principle one can write down Kolmogorov equations for the transition probabilities of the (Q, R, L) process and solve them. However, such a solution must inevitably be numerical. Here we shall write down an approxi- mate system of Ito stochastic differential equations, see Arnold ( 1974) » to describe process evolution, and from them deduce certain useful information valid when c is large. We write, on the basis of (2.2), £(t) 2(t) £(t) dQ(t) = {CA(t)[l-~-] - cA(t)~—- u(t)2(t) + v(t)a(t)[l-^— ]R(t) 2(t) - v(t)a(t)-£— £(t)}dt + /cA(t)[l-— ] dW^t) - /cA(t)-E— dW2(t) / / mi y(t)£(t) dW3(t) + /v(t)a(t)[l~]J(t) dW^t) yv(t)a(t)^— R(t) dWgU) , (2.3) Q(t) Q(t) dR(t) = (2cX(t)^- v(t)a(t)[l- ^— - ]R(t) *** L C ,v> Q(t) + v(t)a(t)=— - R(t) - v(t)a(t)R(t)}dt + 2/cX(t)^- dW2(t) - /v(t)a(t)[l-^--]R(t) dW^Ct) Q(t) + /v(t)a(t)^- R(t) dW5(t) - /v(t)a(t)R(t) dWfi(t) , dL(t) = v(t)a(t)R(t)dt + /v(t)a(t)R(t) dWc(t) where (W. (t), o as t-*» , since L represents cumulative losses. Thus we shall be IS* interested in the first two equations in (2.6), and in (2.7) which we now write as f \ r n dX X dY Y ^ ) dt + D+dW (2.8) and C. (2 x 2) is A. without its last row, while D. (2 x 6) is B. ~L ""L ~t ~t without its last row. Now the bivariate stochastic process described by (2.8) is nonstationary Ornstein Uhlenbeck, since C. has eigenvalues with non-negative real parts; see Arnold (1974), Sec. 8.3, for an account of the scalar case, or see Schach and McNeil (1973). Much that is useful is known about this process. In particular, if (X(0), Y(0)) = 0 , and q(0), r(0) are given, then for all t>0 (X(t), Y(t)) has a bivariate normal distri- #v* r*s bution with mean 0 and covariance matrix E. which satisfies the differ- ential equation i+ = c,s. + z.c: + d.d; ~t ^C^L ~t t ~t~t (2.9) see Arnold (1974), Sec. 8.2. Combining these facts leads to the Result: (£, R) is approximately bivariate normal (Gaussian), as c-*» : (Q(t), R(t)) ~ W(c(q,r), cE.) (2.10) From this expression it is possible to estimate the probability that at least a specified number of channels are occupied at time t , and also to estimate the probability that there are no more than any specified number of customers awaiting re-try. Such quantities are useful measures of system performance. Of course both the deterministic equations (2.6) and the equation (2.9) for the covariance matrix Z. must be solved numerically, but this should be a less difficult step than is the simulation of such a system. Steady-State Results: Suppose A(t)+A , u(t)-ni , v(t)+v , a(t)->a all positive constants, as t-*» . In this case it may happen that q(t)-x| and r(t)->r , the latter satisfying (2.6) with derivatives set equal to zero: 0 = A(l-2q) - yq + avr(l-2q) 0 = 2Aq - avr(l-2q) - avr and these are immediately solved to give (2.11) (2.12) (l+2p) - /(l+2p)2- 8ap : 2p 4a (l+2p) + /(1+2P)2- 8pa p-Q r = — a- a n (2.13) where p = A/y and n - v/y , and provided that the numerical results ob- tained are feasible: 0 (Q-l , R+l , L), and ■+ (Q, R-l, L+l ) , replacing with the transition rate Q Q(t), R - Q(t) + 1, R(t) - 1 , probability v(t)R(t)[l - -]dt (3.1) ~ ~ ~ ~ ~ c Effectively this change in Model 1 prevents losses, and, when a re-try prepares to access an occupied channel, it senses the presence of the on- going message, and refrains before destruction. This model can be analyzed by the technique described for Model 1, namely that of setting up approximating I to-type stochastic differential equations, and then carrying out an expansion for c -* °° . The results are as follows. Deterministic Component: We find that for Model 2 q'(t) = A(l-2q) - uq + vr(l-q) r'(t) = 2Aq - vr(l-q) Stochastic Component: Use of the representation (2.4) together with the stochastic differ ential equations and Ito's lemma yields (3.2) f 1 dX X dY ■*t Y I ~ J . + ?tdwt • (3.3) 11 the s.d.e. for a non-stationary Ornstein-Uhlenbeck process. In this case (suppressing t-dependence) , *t- ■t- -(2A + u + vr) 2A + vr /A(l-q) -Aq" 0 2/Aq v(l-q) -v(l-q) (3.4) Vuq /vr(l-q) 0 -/vr(l-q) (3.5) and St = (yi(t)> ^2(t)' h{t)> y4(t))' ' (3-6) a 4-dimensional standard Wiener process with independent components. Once again the equation (2.9) may be solved for the covariance function I. , with A. substituted for C., and B. in place of D. . And once again we state the Result: (Q, R) is approximately bivariate normal as c -»■ » : (Q, R) ~ W(c(q,r), cZt) (3.7) Steady-State Results: If A(t) -> A , y(t) ->• u , v(t) -> v as t -> °° , then it may happen that q(t) ■* q , and r(t) ■»■ r , these satisfying the equations (3.2) with q = r The solutions are easily obtained, and are A . _ 2A2 _ 2p2 ^ = y = p ' r = vTI^AT = ^T^y ; (3.8) apparently it is necessary that q = p < 1 for steady state to occur. Note that in Model 1 it was necessary that q < 1/2 in order that steady state conditions occur. If we compare Models 1 and 2 when a = 1 we find 12 Model 1 Model 2 q = P , (0 < p < h q = p , (0 < p < 1) r = 2£i r = 2fi! n(l-2p) ' ' njl^ Clearly the setup of Model 2 results in considerably smaller expected wait per unit time (approximated by c(q+r)) than does that of Model 1. The improved service must be purchased in return for investment in the busy channel sensing capacity. The Model 2 can be compared to the model of Gaver and Lehoczky (1976). The steady state covariance matrix, Z , is obtained from (2.14), replacing C by A , and D by B . We find that i i 1 2 22 where = A b(a+b-d) 2b2 b2 bd 2ab ab d2 2ad a(a+b)-bd X + yq + vr(l-q) -(2Xq + vr(l-q) ) 4Xq + vr(l-q) a = 2X + y + vr , b = v(l-q) d = 2X + vr , A = 2ab(d-a-b) + 2b2d (3.9) (3.10) 13 4. Model 3: Transitory Version of Model 1. Consider next a transitory service system version of the basic Model 1. There are N messages to be transmitted, and each initially is transmitted independently and at a time having absolutely continuous distribution function F(t) , with F(0+) = 0 , and density f(t) . Once a given message is trans- mitted, no more appear from its particular source, so even though some messages enter the re-try population one or more times, the traffic gradu- ally fades away; the problem is fundamentally non-stationary. For analysis of a similar problem see Gaver, Lehoczky, and Perlas (1975). The following state variables are required. I(t) = the number of message arrivals that have occurred by time t ; 0 < I(t) < N . Q(t) = the number of messages being transmitted at time t ; 0 < Q(t) < c . R(t) = the number of messages in the re-try population at time t . We assume, as we did in formulating Model 1, that if a newly arriving message encounters a channel -- selected at random -- held by a message in progress, then both are instantly "destroyed," and immediately join R . No messages are ever lost. Messages in R re-try at rate v(t)R(t) . The transition scheme is given below. The individual message arrival rate at time t is seen to be A(t) = f(t)/[l-F(t)] . Transition Probability (t to t+dt) Q (I, Q, R) + (1+1, Q+l, R) X(t)[N - I(t)][l - ^-]dt Q ■+ (1+1, Q-l, R+2) X(t)[N - I(t)]£dt - (I, Q-l, R) y(t)Qdt (4.1) ~ ~ Q + (I, Q+l, R-l) v(t)R[l - =-]dt ~ "" ^Q + (I, Q-l, R+l) v(t)R^dt . 14 From the above we can write down the approximating stochastic differential equations analogous to (2.3 ). These are, suppressing t-dependence state- ments, Q / Q dl = A[N - I]dt + A[N _ i][! . 2.] dw + A[N - I]- dW9 (4.2) dQ = {A[N - I][l - ^] - A[N - IP - yQ - vR- + vR[l - -]}dt + A[N - I][l - §■] d^ - A[N - 1]^ dW2 - /yQ dW3 Q / Q /vRJ- dW. + /vR[l - ^] dW, ~C ~4 ~ C ~D dR = {2A[N - I]£ + vf£ - vR[l- ^]}dt + /Q /Q 2/A^[N - I] dW9 + /vR- dW„ c ~ ~2 ~c ~4 - /vR[l - -] dW, c ~5 Once again we study the behavior of the system as system parameters, in this case both N , the initial number of messages, and c , the number of channels become large. In fact, we relate these parameters as follows: c = $N, 3 being a positive constant. Introduce the noise processes 15 Kt) - Ni(t) X(t) = , Q(t) - Nq(t) Y(t) = , (4.3) R(t) - Nr(t) Z(t) = , where (i(t), q(t), r(t)) = lim (I(t)/c, Q(t)/c, R(t)/c) . Then an application of Ito's lemma and identification of terms of order Ai and N yields the deterministic and stochastic components of the process. Deterministic Equations: i'(t) = A(l - i) q'(t) = A(l - i)(l - q/3) - A(l - i)q/3 - yq - vrq/6 + vr(l - q/3) . (4.4) r'(t) = 2A(1 - i)q/6 + vrq/6 - vr(l - q/g) From the first equation and the definition of A it follows immediately that A(l-i) = f , the density of the arrival distribution. Note that when this substitution is made in the second and third equations the latter are precisely of the form of the corresponding equations of Model 1: Correspondence Between Model 1 and Model 3 Arrivals and Re-tries Model 1 Model 3 A(t) f(t)/3 v(t) v(t)/3 In the present model f(°°) = 0 , and hence the arrival rate is eventually zero, and some time afterwards the system is completely empty. The present model possesses no steady state solution, and to learn about system status at various times it is necessary to solve (4.4) numerically. 16 Stochastic Equations: The expansion technique shows that the noise process satisfies where and ( 1 dX r i X dY ■*t Y dZ s J Z + ! A h- -X 0 0 -A(l-2q/3) -2f/B + U+ 2vr/3 v(l-2q/3) -2Aq/3 2f/3 + 2vr/3 -v(l-2q/3) !t" /f(l-q/3) /fq73 0 0 0 /f(l-q/3) -/fq/3 -4iq -/vrq/3 /vr(l-q/3) /vrq/3 -/vr(l-q/3) 0 2/fq/3 0 (4.4) (4.5) (4.6) and W. is a 5-dimensional standard Wiener process with independent components. Result: (I, Q, R) is approximately normal as N (hence c) -*■ °° (I, Q, R) - W( c(f, q, r), c.Z. ) -N, *** +* ~ L Here £. satisfies the differential equation and ?t!i = 5t = 5t5t + 5tAi + ?tBt f f(l-2q/3) 2 fq/3 f(l-2q/3) f(l-2q/3) + yq + vr -(2fq/3 + vr) 2fq/3 -(2fq/3 + vr) 4fq/3 + vr (4.7) (4.8) 17 As might be anticipated, the fact that Var[I(t)] = a (t) + F(t)[l-F(t)] (4.9) 1 1 may be deduced from (4.7) 18 5. Model 4: Transmission to Completion in Model 1. Suppose now, as may be quite realistic, that a message attempting to transmit on a channel does so until completion before it discovers that it has been "destroyed," i.e. garbled by others—which it also contributes to garbling. The analysis at once becomes much more complex because a channel may contain any number of destroyed messages. Our formulation is that of Model 1, save for the change described above. The following state variables describe the system. Q(t) = the number of channels carrying good, i.e. ungarbled or unde- stroyed messages at time t . S. (t) = the number of channels carrying exactly k messages that are destroyed at time t ; clearly S (t) = Q(t) , and oo 0 < Q + IS, < C. ~ k=rK R(t) = the number of messages in R at time t . The transition probability scheme is summarized next. We write S,(t) = Z S.(t) . k=o~K 19 Transitions Probabilities (Q. §r S2,..., Sk,..., R) + Q+S, (Q+l, S,,..., S. ,..., R) CX[1 - =-^]dt Q+S+ (Q+l, S^..., Sk,...s R-l) VR[1 - — — ]dt (Q-l, Sr..., sk,..., R) yqdt Q (Q-l, Sr S2+l ,. . . , Sk,..., R-l) vFRJt CA- (Q-l, Sr S2+l,..., Sk,..., R) (Q, Sr..., Sk+1,...5 R-l) s (5.1) for k = 1, 2, 3, ... vR^dt (Q, Sr..., Sk-1, Sk+1,..., R) cX^dt ~c h c sl (Q, S,-l,..., S. R+l) y^dt (Q, Sr..., Sk+1, Sk+1-1,..., R+l) y(k+l)S k+1 There will be a denumerable infinity of such transitions. While it is in principle possible to carry out the expansion technique, we shall content our- selves with a brief discussion of the deterministic equations analogous to (2.6). Following the example of Section 2, we can write down these differ- ential equations for the limits as c+°° of Q/c , R/c , and S./c (k=l,2,...), denoted by q , r , and s, : 20 q' = - (A + vr)(l - s+ - q) - (y + A + vr)q oo r' = - vr + y £ ks. k=l (5.2) s^ = y(k+l)sk+1 + (A+vr)s|<_1 - (k+A+vr)sk , k=l ,3,4,5, .. . s£ = 3ys3 + (A+vr)(s-,+q) - (2y+A+vr)s2 The steady-state values, which exist under circumstances to be derived, are obtained by solving the above system of equations with the derivatives set equal to zero. To simplify, first divide through by y , putting p = A/y , n = v/y . After some algebra it is found that q = P (5.3) p + nr = 6 , so r = (e - p)n_1 (5.4) where 6 is the smallest solution of the equation e"x = p , (5.5) 1+x provided one exists S] = p0 e-eek sk = TT-> k^2 (5.6) Further analysis shows that in order for a steady-state to exist, p$£^e-(*-l>/2. 0.20588... A + 1 Notice that this value is much smaller than the just-intolerable value of 1/2 derived from Model 1. Clearly, transmission to completion of messages provides opportunity for many more transmissions to be destroyed. 21 6. Model 5: Transmission to Completion with Intelligent Re-tries A natural variation of the previous model is obtained by insisting on transmission to completion, but also allowing for an intelligent re-try capability, as in Model 2. This means that the transitions -(Q-l, Sr S2+l,.., Sk,.., R-l) , and -(Q, Sp..., Sk+1>..., R-l) are ruled out, i.e. have probability zero in this model. Consequently the tran- sition rates of (5.1) apply, with this change. Confining attention to the deterministic differential equations it may be shown that these have the form given below. q' = (A+vr)(l - S+ - q) - (A+y)q r' = -vr(l - s - q) + u I ks. k=l K s£ = (k+1) ysk+1 + Xsk_1 - (X+ky)sk s« = 3us~ + As-, - (A+2u)s2 + Xq . Once again let p=A/u, n=v/u, and solve for the steady-state values (6.1) These are q = P r - 1 P[(1+P)ep-1] n l-(l+p)(ep-l) S-|= p (6.2) (6.3) (6.4) (6.5) sk= (1+P)fr > k=2,3,... The condition for existence of a steady state is that the denominator of (6.3) be positive, which translates into the requirement that p < 0.50855... The latter value may be contrasted to the just-tolerable value of unity derived for Model 2. 22 7. Numerical Results for Model 1. In order to check the quality of the diffusion approximations, a simulation program was written that realizes the two-dimensional Markov process describing Model 1. The latter was then exercised through 5 x 10 state changes for several values of the offered load, A/u , and for several channel numbers; the parameter a = 1 , and v/u = 0.08 in this experiment. The results were generally supportive of the approxima^ tion, as is seen by examining the following tables. Note, however, that assessments of the mean and variance of the number of active channels, Q , are generally in closer agreement than are those for the size, R , of the re-try population. 23 TABLE 1. Means and Variance-Covariance Values by Simulation and Diffusion Approximation c = 10 ; v/u = 2.0 X/u: 0.48 0.40 0.32 0.20 E[Q] simulat. 4.79 3.99 3.19 1.99 diffus. 4.80 4.0 3.2 2.0 Var[Q] 2.52 2.52 2.38 1.76 2.50 2.52 2.39 1.77 E[R] 65.13 9.31 3.29 0.75 57.6 8.0 2.84 0.67 Var[R] 1470. 50.26 10.62 1.57 1466. 42.81 8.80 1.35 Cov[R,Q] 0.034 0.124 0.166 0.149 0.038 0.143 0.177 0.150 24 TABLE 2. Means and Variance-Covariance Values by Simulation and Diffusion Approximation c = 25 ; v/u = 2.0 X/y • 0.48 0.40 0.36 0.20 E[Q] simulat. 11.95 9.97 7.98 4.99 diffus. 12.0 10.0 8.0 5.0 Var[Q] 6.32 6.31 5.98 4.41 6.26 6.30 5.97 4.42 E[R] 149.5 21.11 7.49 1.73 144.0 20.0 7.11 1.67 Var[R] 3524. 110.2 23.74 3.56 3666. 107 22.0 3.38 Cov[R,Q] 0.041 0.132 0.177 0.150 0.040 0.143 0.177 0.150 25 8. Summary and Conclusions In this paper it has been shown that an approximate approach, using stochastic differential equations, is effective for modeling an element of a complex communication system. The approximation improves as c , the number of channels available for transmission, becomes large. The adequacy of the model under such conditions is suggested by the theoretical results of Barbour (1974) and Kurtz (1971); numerical solutions of selected systems also attest to the adequacy of the approximation. The authors wish to gratefully acknowledge the research support of the Office of Naval Research 26 REFERENCES [1] Arnold, Ludwig (1974). Stochastic Differential Equations: Theory and Applications. Wiley-Interscience. John Wiley and Sons, New York. [2] Barbour, A. (1974). "On a functional central limit theorem for Markov population processes." Advances in Appl . Prob., 6_, No. 1. [3] Gaver, D.P., Lehoczky, J. P., and Perlas, M. (1975). "Service systems with transitory demand." In Logistics , Vol. 1 of North Holland TIMS Studies in Management Science. North-Holland/American Elsevier, New York and Amsterdam. [4] Gaver, D.P.,and Lehoczky, J. P. (1976). "Gaussian approximation to service problems: a communication system example." Journal of Appl . Prob., 13. [5] Kleinrock, L. (1976). Queueing Systems, Vol. II. Wiley-Interscience. John Wiley and Sons, New York. [6] Kurtz, T. (1971). "Limit theorems for sequence of jump Markov pro- cesses approximating ordinary differential equations." Journal of Appl. Prob., 8, No. 2. [7] Schach, S., and McNeil, D.R. (1973). "Central limit analogues for Markov population processes," Journal of Royal Stat. Soc. (B), 35_, No. 1 27 Distribution List Copies Defense Documentation Center 2 Cameron Station Alexandria, Virginia 22314 Dean of Research 1 Code 023 Naval Postgraduate School Monterey, California 93940 Library (Code 0212) 2 Naval Postgraduate School Monterey, California 93940 Library (Code 55) 2 Naval Postgraduate School Monterey, California 93940 D. P. Cox 1 Department of Mathematics Imperial College London, SW7 England D. R. McNeil 1 Department of Statistics Princeton University Princeton, New Jersey 08540 J. A. Hooke 1 E. Wolman 1 Bell Telephone Labs Holmdel, New Jersey 07733 B. J. McDonald 1 Office of Naval Research 800 N. Quincy Street Arlington, Virginia 22217 L. Kleinrock 1 R. Muntz 1 Computer Science University of California Los Angeles, California 90024 J. M. Wozencraft 1 Electrical Engineering M . I . T . Boston, Massachusetts 02139 28 Copies U . 1- . I ^ I L'lld I L ± Depai tment of Operations Kcsoarch Stan ford University Stanford, California 94305 j. R iordan 1 Department of Mathematics Rockefeller University New York, New York 10021 G. Fishman 1 University of North Carolina Chapel Hill, North Carolina 27514 P. T. Holmes 1 Department of Mathematics Clemson University Clemson, South Carolina 29631 R. Elashoff 1 Biomat hematics University of California Los Angeles, CA 90024 Gene Fisher 1 Management Science Department RAND Corporation 1700 Main Street Santa Monica, California 90401 R. M. Stark 1 Statistics and Computer Science University of Delaware Newark, Delaware 19711 M. Mazumdar 1 Robert Hooke 1 Mathematics Department Westinghouse Research Labs Churchill Boro Pittsburgh, Pennsylvania 15235 J. R. Capra 1 Center for Naval Analysis 1401 Wilson Boulevard Arlington, Virginia 22209 Roy Welsch 1 Sloan School M. I . T. Cambridge, Massachusetts 02139 29 Copies J . U . B 1 uai 1 B. K. A